package leetcode.code0738;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	public int monotoneIncreasingDigits(int n) {
		int[] nums = new int[11];
		int pnum = 0;
		int tmp = n;
		while (tmp > 0) {
			int last = tmp % 10;
			nums[pnum++] = last;
			tmp = tmp / 10;
		}
		int last = 0;
		// 6688 41
		int p = pnum - 1;
		while (p >= 0) {
			if (nums[p] >= last) {
				last = nums[p];
				p--;
			} else {
				while (p < pnum && p + 1 < pnum && nums[p] < nums[p + 1]) {
					p++;
					nums[p] -= 1;
				}
				break;
			}
		}
		int ans = 0;
		int i = pnum - 1;
		for (; i >= p && i >= 0; i--) {
			ans = ans * 10 + nums[i];
		}
		while (i >= 0) {
			ans = ans * 10 + 9;
			i--;
		}
		return ans;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(1234, this.monotoneIncreasingDigits(1234));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub
		HelpDebug.compare(299, this.monotoneIncreasingDigits(332));
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub
		HelpDebug.compare(667999, this.monotoneIncreasingDigits(668841));
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
